#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include <functional>
using namespace std;

namespace lh
{
    //BM48 数据流中的中位数
    //https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=295&tqId=23457&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution {
    public:
        priority_queue<int, vector<int>>min;//前半部分的大顶堆
        priority_queue<int, vector<int>, greater<int>>max;//后半部分的小顶堆
        //个人认为大顶堆是抽象的倒着放在平面的
        //其实抽不抽象都无所谓，因为我们每次都会重写排序，取top就好），实现升序
        void Insert(int num) {
            //第一步无脑入前半部分的堆
            min.push(num);
            //第二步将前半部分堆的最大值移到后半部分小堆，加入2个数据，实现前面一个后面一个
            max.push(min.top());
            min.pop();
            //第三步判断，我们就要求前半部分的堆必定比后半部分的堆至多 多1个数据
            if (min.size() < max.size())
            {
                //如果不是，则我们把后半部的堆的top放入前半部分(小顶堆最小值放入大顶堆)
                min.push(max.top());
                max.pop();
            }
        }

        double GetMedian() {
            //根据我们的规定，如果前半部分比后半部分多1个就是奇数 
            if (min.size() > max.size())
            {
                return (double)min.top();
            }
            else
                return (double)(min.top() + max.top()) / 2;
        }
    };
    void test()
    {
        vector<int>num{ 5,2,3,4,1,6,7,0,8 };
        Solution s;
        for (int i = 0; i < num.size(); i++)
        {
            s.Insert(num[i]);
            cout << s.GetMedian() << endl;
        }
    }

    //BM83 字符串变形
    //https://www.nowcoder.com/practice/c3120c1c1bc44ad986259c0cf0f0b80e?tpId=295&tqId=44664&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        string trans(string s, int n) {
            //反转空格区间字符串，再反转整个字符串
            //大小写转化
            for (auto& e : s)
            {
                if (e >= 'a' && e <= 'z')
                {
                    e = e - 'a' + 'A';
                }
                else if (e >= 'A' && e <= 'Z')
                {
                    e = e - 'A' + 'a';
                }
            }
            //反转空格区间字符串
            for (int i = 0; i < n; i++)
            {
                int j = i;
                //跳过一整个单词
                while (j < n && s[j] != ' ')
                    j++;
                reverse(s.begin() + i, s.begin() + j);
                //更新遍历起始位置
                i = j;
            }
            //反转整个字符串
            reverse(s.begin(), s.end());
            return s;
        }
    };
    void test2()
    {
        string s = "This is a sample";
        cout << s << endl;
        int n = 16;
        string res=Solution2().trans(s, n);
        cout << res << endl;
    }
}

int main()
{
    lh::test();
    lh::test2();
    return 0;
}